#include"const.h"
#include <algorithm>
/*
* 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，
分别表示 nums1 和 nums2 中的元素数目。  请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。  
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，
后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
*/
namespace Merge_Shorted_Array01
{	//第一种方法，我们只需要将nums2中的元素移动到nums1中为0的位置，再进行排序即可
	class Solution
	{
	public:
		void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n)
		{
			int i = 0;
			for (; i < n; i++)
			{
				nums1[i+m] = nums2[i];
			}
			std::sort(nums1.begin(), nums1.end());
		}
	};
}
namespace Merge_Shorted_Array02
{	//第二种方法，采用两个指针，类似于归并排序
	class Solution
	{
	public:
		void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n)
		{
			int i = 0;
			std::vector<int> tmp(m+n);
			int it1 = 0;
			int it2 = 0;
			while (it1 < m && it2 < n)
			{
				if (nums1[it1] < nums2[it2])
				{
					tmp[i++] = nums1[it1++];
				}
				else
				{
					tmp[i++] = nums2[it2++];
				}
				
			}
			//将nums1或nums2中还没有放到tmp中的元素放入
			//此时it1或者it2一定有一个已经走完了
			while (it1 < m)
			{
				tmp[i++] = nums1[it1++];
			}
			while (it2 < n)
			{
				tmp[i++] = nums2[it2++];
			}
			nums1 = std::move(tmp);
		}
	};
	
}
